import kotlin.math.min

object SelectSort {
    fun <E : Comparable<E>> sort(l: MutableList<E>) {
        for (i in l.indices) {
            var miniIndex = i

            for (j in i until l.size) {
                if (l[j] < l[miniIndex]) {
                    miniIndex = j
                }
            }
            exchange(i, miniIndex, l)
        }
    }

    private fun <E> exchange(a: Int, b: Int, l: MutableList<E>) {
        val temp = l[a]
        l[a] = l[b]
        l[b] = temp
    }
}

object InsertSort {
    fun <E : Comparable<E>> sort(l: MutableList<E>) {
        for (i in l.indices) {
            var j = i
            val temp = l[i]
            while (j > 0 && l[j - 1] > temp) {
                l[j] = l[j - 1]
                j -= 1
            }
            l[j] = temp
        }
    }
}

object MergeSort {
    fun <E : Comparable<E>> sort(l: MutableList<E>) {
        sortByRecursion(l, 0, l.size - 1)
    }

    private fun <E : Comparable<E>> sortByRecursion(l: MutableList<E>, left: Int, right: Int) {
        if (right <= left) {
            return
        }

        val mid = left + (right - left) / 2
        sortByRecursion(l, left, mid)
        sortByRecursion(l, mid + 1, right)
        if (l[mid] > l[mid + 1]) {
            merge(l, left, mid, right)
        }
    }

    fun <E : Comparable<E>> sortFromBelow(arr: MutableList<E>) {
        var step = 1
        val size = arr.size
        while (step < size) {
            var left = 0
            while (left + step < size) {
                val right = min(left + step * 2 - 1, size - 1)
                val mid = left + step - 1
                if (arr[mid] > arr[mid + 1]) {
                    merge(arr, left, mid, right)
                }
                left += step * 2
            }

            step *= 2
        }
    }

    private fun <E : Comparable<E>> merge(arr: MutableList<E>, left: Int, mid: Int, right: Int) {
        val temp = arr.slice(left..right)
        var n = left
        var i = left
        var j = mid + 1
        while (n <= right) {
            if (i > mid) {
                arr[n] = temp[j - left]
                j += 1
            } else if (j > right) {
                arr[n] = temp[i - left]
                i += 1
            } else if (temp[i - left] <= temp[j - left]) {
                arr[n] = temp[i - left]
                i += 1
            } else if (temp[i - left] > temp[j - left]) {
                arr[n] = temp[j - left]
                j += 1
            }
            n += 1
        }
    }
}

object QuickSort {
    fun <E: Comparable<E>> sort(arr: MutableList<E>) {
        sortByRecursion(arr, 0, arr.size - 1)
    }

    private fun <E: Comparable<E>> sortByRecursion(arr: MutableList<E>, left: Int, right: Int) {
        if (left >= right) {
            return
        }

        val j = partition(arr, left, right)
        sortByRecursion(arr, left, j)
        sortByRecursion(arr, j+1, right)
    }


    private fun <E: Comparable<E>> partition(arr: MutableList<E>, left: Int, right: Int): Int {
        randomV(arr, left, right)

        val v = arr[left]
        var i = left + 1
        var j = left
        while (i <= right) {
            if (arr[i] < v) {
                j += 1
                exchange(arr, i, j)
            }
            i += 1
        }
        exchange(arr, left, j)
        return j
    }

    fun <E: Comparable<E>> sortThreeWays(arr: MutableList<E>) {
        sortByRecursionThreeWays(arr, 0, arr.size - 1)
    }

    private fun <E: Comparable<E>> sortByRecursionThreeWays(arr: MutableList<E>, left: Int, right: Int) {
        if (left >= right) {
            return
        }

        val (lessThan, greatThan) = partitionThreeWays(arr, left, right)
        sortByRecursionThreeWays(arr, left, lessThan)
        sortByRecursionThreeWays(arr, greatThan, right)
    }

    private fun <E: Comparable<E>> partitionThreeWays(arr: MutableList<E>, left: Int, right: Int): Pair<Int, Int> {
        randomV(arr, left, right)

        val v = arr[left]
        var i = left + 1
        var lessThan = left
        var greatThan = right + 1
        while (i < greatThan) {
            if (arr[i] < v) {
                lessThan += 1
                exchange(arr, i, lessThan)
                i += 1
            }else if (arr[i] == v) {
                i += 1
            }else if (arr[i] > v) {
                greatThan -= 1
                exchange(arr, i, greatThan)
            }
        }
        exchange(arr, lessThan, left)

        return Pair(lessThan, greatThan)
    }

    private fun <E> exchange(l: MutableList<E>, a: Int, b: Int) {
        val temp = l[a]
        l[a] = l[b]
        l[b] = temp
    }

    private fun <E>randomV(arr: MutableList<E>, left: Int, right: Int) {
        val p = kotlin.random.Random.nextInt(0, right - left + 1) + left
        exchange(arr, left, p)
    }
}

fun main() {
    val l1 = ArrayGenerator.generateRandomArray(20)
    QuickSort.sortThreeWays(l1)
    println(l1)
}